package com.xk._02算法篇._06greedy.ks;

import java.util.*;

/**
 * @description:
 * @author: xu
 * @date: 2022/10/17 21:38
 */
public class Knapsack {
    private static Article[] articles = new Article[]{
            new Article(35, 10), new Article(30, 40),
            new Article(60, 30), new Article(50, 50),
            new Article(40, 35), new Article(10, 40),
            new Article(25, 30)
    };

    public static void main(String[] args) {
        select("价值主导：", (a1, a2) -> a2.value - a1.value);
        select("重量主导：", (a1, a2) -> a1.weight - a2.weight);
        select("价值密度主导：", (a1, a2) -> Double.compare(a2.valueDensity, a1.valueDensity));
    }

    static void select(String title, Comparator<Article> comparator) {
        Arrays.sort(articles, comparator);

        int capacity = 150, weight = 0, values = 0;
        List<Article> selectedArticles = new LinkedList<>();
        for (int i = 0; i < articles.length && weight < capacity; i++) {
            int newWeight = weight + articles[i].weight;
            if (newWeight <= capacity) {
                weight = newWeight;
                values += articles[i].value;
                selectedArticles.add(articles[i]);
            }
        }
        System.out.println(title);
        System.out.println("总价值：" + values);
        for (Article selectedArticle : selectedArticles) {
            System.out.println(selectedArticle);
        }
        System.out.println("======================================");
    }
}
